package LeetCode200_300;

/**
 * 201. 数字范围按位与
 * 给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）
 *
 *  思路：最直观的方式就是按位与运算的性质。  最笨的办法就是迭代范围内的每个数字，然后按位与，但是这样肯定不行，空间复杂度不允许这样。
 *         可以利用公共前缀的思想去这么干,利用公共前缀移位，就可以统计出按位与的个数。
 *  算法思路： 1： 通过右移，将两个数字压缩为它们的公共前缀，在迭代的过程中，我们计算执行的右移操作数；
 *           2： 将得到的公共前缀左移就是返回的所有结果。
 */
public class LeetCode_201 {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right){
            left = left >> 1;
            right = right >>1;
            shift++;
        }
        return left<< shift;
    }
}
